// 求图的强连通分量
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\2_Adjacency_Matrix\Adj_Matrix.h"

int finish[MAX] = {0};
int visited[MAX] = {0};
int count = -1;
void DFS(Adj_Matrix G, int v)
{
    visited[v] = 1;
    for (int i = 0; i < G.node_num; i++)
    {
        if (G.M[v][i] != 0 && G.M[v][i] != INFINITY)
        {
            if (!visited[i])
            {
                DFS(G, i);
            }
        }
    }
    finish[++count] = v;
}
void frsit_DFS(Adj_Matrix G)
{
    for (int i = 0; i < G.node_num; i++)
    {
        if (!visited[i])
            DFS(G, i);
    }
}
Adj_Matrix contray(Adj_Matrix G)
{
    Adj_Matrix G_copy;
    G_copy.node_num = G.node_num;
    for (int i = 0; i < G.node_num; i++)
    {
        G_copy.data[i] = G.data[i];
        for (int j = 0; j < G.node_num; j++)
        {
            G_copy.M[i][j] = G.M[j][i];
        }
    }
    return G_copy;
}
void s_DFS(Adj_Matrix G, int v)
{
    visited[v] = 1;
    for (int w = 0; w < G.node_num; w++)
    {
        if (G.M[v][w] != 0 && G.M[v][w] != INFINITY && !visited[w])
            s_DFS(G, w);
    }
    printf("%3d", G.data[v]);
}
void second_DFS(Adj_Matrix G)
{
    for (int i = 0; i < MAX; i++)
        visited[i] = 0;
    for (int i = count; i >= 0; i--)
    {
        if (!visited[finish[i]])
        {
            s_DFS(G, finish[i]);
            printf("\n");
        }
    }
}
void kosaraju(Adj_Matrix G)
{
    // 1. 一次DFS  finish[]
    frsit_DFS(G);
    // 2. 取反
    Adj_Matrix G_copy = contray(G);
    // 3. 二次DFS
    second_DFS(G_copy);
}

int main()
{
    /*******************code*******************/
    Adj_Matrix G;
    creat_kosaraju(G);
    kosaraju(G);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
